//
// Created by spiro on 19-4-15.
//

#ifndef INTRODUCTION_TO_ALGORITHMS_BIN_TREE_H
#define INTRODUCTION_TO_ALGORITHMS_BIN_TREE_H

#include <stdbool.h>

typedef int Key;

typedef struct btnode {
    Key key;
    struct btnode * parent;  // parent node
    struct btnode * left;
    struct btnode * right;
} BTNode;

typedef struct bintree {
    BTNode * root;
    int size;
} BinTree;

/**
 * Compare key, 
 *  k1 greater than k2 return positive integer;
 *  k1 equal to k2 return zero;
 *  k1 less than k2 return negative.
 */
int KeyCompare(Key k1, Key k2);

/**
 * determine whether tree is empty
 */
bool IsEmpty(BinTree * tree);

/**
 * Initialize tree
 */
void TreeInitialized(BinTree * tree);

/**
 * Print tree node key in order
 */
void TreeInorderWalk(BinTree * tree, void (*func)(Key));

/**
 * Search a node by key
 */
BTNode * TreeSearch(BinTree * tree, Key);

/**
 * Get node pointer who's key is minimum
 */
BTNode * TreeMinimum(BinTree * tree);

/**
 * Get node pointer who's key is maximum
 */
BTNode * TreeMaximum(BinTree * tree);

/**
 * Get predecessor node pointer of a node
 */
BTNode * TreePredecessor(BTNode * node);

/**
 * Get successor node pointer of a node
 */
BTNode * TreeSuccessor(BTNode * node);

/**
 * Insert a new node in tree for key
 */
BTNode * TreeInsert(BinTree * tree, Key key);

/**
 * Delete a node from tree
 */
void TreeDelete(BinTree * tree, BTNode * node);

/**
 * Delete all node and release all mem.
 */
void TreeRelease(BinTree * tree);

#endif //INTRODUCTION_TO_ALGORITHMS_BIN_TREE_H
